package com.leo.basic.chapter06.unionFindSet;

/**
 * 可以改进的方向：维护每个节点的子节点 个数，union的时候，将个数少的节点连接到个数多的节点上面
 * @author xuexiaolei
 * @version 2017年12月13日
 */
public class UFS04 {
    private int[] mParents;
    //新加一个数组用来记录每一个节点,以它为根的元素的个数。
    //mSize[i]表示以i为根的树结构中的元素个数。
    private int[] mSize;
    private int mCount;

    public UFS04(int capacity){
        mCount = capacity;
        mParents = new int[mCount];
        mSize = new int[mCount];
        for (int i = 0; i < mCount; i++) {
            mParents[i] = i;
            //默认每个都是1：独立的时候含有一个元素.
            mSize[i] = 1;
        }
    }
    //以下find和isConnected都用不到mSize.
    public int find(int p){
        if( p<0 || p>=mCount){
            //...做一些异常处理
        }
        while(p!=mParents[p]){
            p = mParents[p];
        }
        return p;
    }
    public boolean isConnected(int p,int q){
        return find(p)==find(q);
    }
    //联合的时候就需要用到mSize了.看看那个节点为根的树形集合中元素多，
    //然后把少的那个节点对应的根，指向多的那个节点对应的根。
    public void union(int p,int q){
        //前两步不变
        int pRoot= find(p);
        int qRoot = find(q);
        if(pRoot == qRoot){
            return;
        }
        int pSize = mSize[pRoot];//初始事都是根，为1
        int qSize = mSize[qRoot];
        //如果pRoot为根的树形集合含有的元素比qRoot的多
        if(pSize > qSize){
            //注意是少的索引的父节点指向多的
            mParents[qRoot] = pRoot;
            //注意此时mSize的改变,由于qRoot归并到了pRoot当中那么
            //需要加上相应数量的size，注意qRoot对应的size并没有改变
            mSize[pRoot] = pSize+qSize;
        }/*else if(pSize < qSize){//同理
            mParents[pRoot] = qRoot;
            mSize[qRoot] = pSize+qSize;
        }else{//如果两个相等那么就无所谓了，谁先合并到谁都可以.
            mParents[qRoot] = pRoot;
            mSize[pRoot] = pSize+qSize;
        }*/
        //然后就可以把等于的合入到大于或者小于的里面.
        else{//此处把小于和等于合到一块
            mParents[pRoot] = qRoot;
            mSize[qRoot] = pSize+qSize;
        }
    }
}
